package mao.leetcode.others.leetcode1011;

class Solution {

    private int[] weights;
    private int n;
    private int D;
    public int shipWithinDays(int[] weights, int D) {
        this.weights = weights;
        this.n = weights.length;
        this.D = D;

        int max =0;
        for(int i=0;i<n;i++){
            max += weights[i];
        }
        int min = (int)(max/D);

        while(min < max){
            int mid = min+(max-min)/2;
            if(helper(mid)){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        return max;
    }

    public boolean helper(int capcity){
        int d = 0;
        int weightOn = 0;
        for(int i=0;i<n;i++){
            //最大货物重量
            if (weights[i] > capcity) return false;
            if(weightOn+weights[i] <= capcity){
                weightOn+=weights[i];
            }else{
                d +=1;
                weightOn=weights[i];
            }
        }

        if(d< D || (d == D && weightOn == 0)){
            return true;
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int day = 5;
        Solution solution = new Solution();
        int i = solution.shipWithinDays(weights, day);
        System.out.println(i);
    }

}